#include <cstdio>

int main( )
{
    int f[ 1001 ][ 3 ], i, n;
    f[ 1 ][ 0 ] = 0;
    f[ 1 ][ 1 ] = f[ 1 ][ 2 ] = 1;
    for ( i = 2; i <= 1000; i++ )
    {
        f[ i ][ 0 ] = ( f[ i - 1 ][ 1 ] + f[ i - 1 ][ 2 ] ) % 10000;
        f[ i ][ 1 ] = ( f[ i - 1 ][ 0 ] + f[ i - 1 ][ 2 ] ) % 10000;
        f[ i ][ 2 ] = ( f[ i - 1 ][ 0 ] + f[ i - 1 ][ 1 ] ) % 10000;
    }
    while ( scanf("%d", &n) && n )
        printf("%d\n", f[ n ][ 0 ]);
    return 0;
}
